package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         32,
		Discription: "最长有效括号子串",
		Level:       3,
		Labels: map[string]int{
			"栈": 1,
			"虚拟栈底": 1,
		},
	})
}

// LongestValidParentheses 用数组下标进栈
//  @param s
//  @return int
func LongestValidParentheses(s string) int {
	n := len(s)
	if n <= 1 {
		return 0
	}

	maxLen := 0
    //栈底始终是往前第一个不匹配的下标(也是当前子串开始的前一个位置)
	indexS := []int{-1}
	for i := range s {
		ch := s[i]
		if ch == '(' {
			indexS = append(indexS, i)
		} else {
			if len(indexS) == 1 {
                //表示栈是空的，再来一个')'之前的就都不匹配了，更新栈底值
				indexS[0] = i
			} else {
                //先出栈再算长度，top后面的子串都是已经匹配好的
				indexS = indexS[:len(indexS)-1]
				maxLen = max(maxLen, i-indexS[len(indexS)-1])
			}
		}
	}

	return maxLen
}